package top.hkyzf.study.leetcode.string;

import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 朱峰
 * @date 2022-1-29 12:01
 */
public class 字母大小写全排列_784 {
    public List<String> letterCasePermutation1(String s) {
        char[] charArray = s.toCharArray();
        List<String> result = new LinkedList<>();
//        Deque<Character> trace = new LinkedList<>();
        StringBuilder trace = new StringBuilder();
        StringBuilder sb = new StringBuilder();
        int temp = 0;
        for (int i = 0; i < s.length(); i++) {
            // 判断是否是字母
            if (charArray[i] >= 'a' && charArray[i] <= 'z') {
                temp++;
                sb.append(s.charAt(i));
                sb.append((char)(s.charAt(i) - 32));
            } else if (charArray[i] >= 'A' && charArray[i] <= 'Z') {
                temp++;
                sb.append(s.charAt(i));
                sb.append((char)(s.charAt(i) + 32));
            } else {
                sb.append(s.charAt(i));
            }
        }
        if (temp == 0) {
            result.add(s);
            return result;
        }
        dfs1(sb, s.length(), 0, trace, result);
        return result;
    }

    void dfs1(StringBuilder sb, int k, int begin, StringBuilder trace, List<String> result) {
        if (k == trace.length()) {
            result.add(trace.toString());
            return;
        }

        for (int i = begin; i < sb.length(); i++) {
            if (check(trace, sb.charAt(i))) {
                continue;
            }
            trace.append(sb.charAt(i));
            dfs1(sb, k, i + 1, trace, result);
            trace.deleteCharAt(trace.length()-1);
        }
    }
    boolean check(StringBuilder sb, Character ch) {
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) == ch || sb.charAt(i) == ch+32 || sb.charAt(i) == ch-32) {
                return true;
            }
        }
        return false;
    }

    public List<String> letterCasePermutation(String s) {
        List<String> result = new LinkedList<>();
        StringBuilder trace = new StringBuilder();
        dfs(0, s, trace, result);
        return result;
    }

    private void dfs(int index, String s, StringBuilder trace, List<String> result) {
        if (s.length() == trace.length()) {
            result.add(trace.toString());
            return;
        }
        char ch = s.charAt(index);
        trace.append(ch);
        dfs(index+1, s, trace, result);
        trace.deleteCharAt(trace.length()-1);

        // 不是数字
        if (!Character.isDigit(ch)) {
            ch = (char) (Character.isLowerCase(ch) ? ch-32 : ch+32);
            trace.append(ch);
            dfs(index+1, s, trace, result);
            trace.deleteCharAt(trace.length()-1);
        }
    }

    @Test
    public void testLetterCasePermutation () {
        String s = "a1b2";
        System.out.println(letterCasePermutation(s));
    }
}
